//定义bfs使用的基础节点，基础节点提供派生类必须实现的接口
function baseNode() {
    this.parent = null;  //上一节点
    this.actionDesc = "" //动作描述,描述了上一节点通过什么样的方式变化为该节点
}

//获取该节点的所有变化节点
baseNode.prototype.getNextStates = function() {
    console.error('baseNode.getNextStates: 你的派生类必须实现它');
    return null
}

//判断两个节点是否相等
baseNode.prototype.equal = function(node) {
    console.error('baseNode.equal: 你的派生类必须实现它');
    return null
}

//输出调试信息
baseNode.prototype.dump = function() {
    console.error('baseNode.dump: 你的派生类必须实现它');
    return null
}

/** 
 * 广度优先搜索 
 * @param Vs 起点 
 * @param Vd 终点 
 */  
//参考: https://blog.csdn.net/g11d111/article/details/76169861
function bfs(vs, vd){
    let blacklist = {}
    let graylist = [];  
    let vn, vw;  

    //初始状态将起点放进队列Q  
    graylist.push(vs);
    //设置节点已经访问过了！
    blacklist[vs.normalize.join()] = vs;

    while (graylist.length > 0){//队列不为空，继续搜索！  
        //取出队列的头Vn  
        //并从队列中移除  
        vn = graylist.shift()

        let states = vn.getNextStates();
        if(!states){
            return false;
        }
        for(vw of states) //Vw = Vn通过某规则能够到达的节点
        {
            let nodeinfo = vw.dump()
            if(!nodeinfo){
                return;
            }
            console.log('vw=',nodeinfo)
            if (!(vw.normalize.join() in blacklist)){  
                //Vw是一个合法的节点并且为白色节点
                vw.parent = vn;
                graylist.push(vw);//加入队列Q
                blacklist[vw.normalize.join()] = vw;//设置节点颜色  
            }
            let findEnd = vw.equal(vd);
            if(!findEnd){
                return false;
            }
            if(findEnd){//找到终点了！  
                //把路径记录
                let trace = []
                let p = vw
                while(p){
                    trace.push(p)
                    p = p.parent
                }
                trace.reverse();
                console.log('结果:')
                for(v of trace)
                {
                    console.log(v.dump())
                }
                return trace;//返回  
            }  
        }  
    }  
    console.log('fail')
    return null;//无解  
}
